package com.kingwood.algorithm.test;

import java.util.*;

/**
 * @Author 22025812
 * @Description: 二叉树相关的题目
 * @Date: 2024/2/28 10:49
 * @Modified By：
 * @Version 1.0
 */
public class ErChaShu {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 递归前序、中序、后序 遍历树
     * https://www.bilibili.com/video/BV12p4y1V728
     * @param root
     */
    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public static void afterOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        afterOrder(root.left);;
        afterOrder(root.right);
        System.out.print(root.val + " ");
    }

    /**
     * 非递归前序、中序、后序 遍历树
     * https://www.bilibili.com/video/BV15P411t7e2
     * @param root
     */
    public static void preOrder2(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                root = stack.pop();
                System.out.print(root.val + " ");

                if (root.right != null) {
                    stack.push(root.right);
                }
                if (root.left != null) {
                    stack.push(root.left);
                }
            }
        }
    }

    public static void inOrder2(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    root = stack.pop();
                    System.out.print(root.val + " ");
                    root = root.right;
                }
            }
        }
    }

    /**
     * 后序非递归遍历，两个栈实现
     * @param root
     */
    public static void afterOrder2(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> collect = new Stack<>();
            stack.push(root);

            while (!stack.isEmpty()) {
                root = stack.pop();
                collect.push(root);

                if (root.left != null) {
                    stack.push(root.left);
                }
                if (root.right != null){
                    stack.push(root.right);
                }
            }

            while (!collect.isEmpty()) {
                System.out.print(collect.pop().val + " ");
            }
        }
    }

    /**
     * 后序遍历，非递归版，一个栈实现
     * @param root
     */
    public static void afterOrder3(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);

            while (!stack.isEmpty()) {
                TreeNode cur = stack.peek();
                if (cur.left != null && root != cur.left && root != cur.right) {
                    // 有左树，且左树没处理过
                    stack.push(cur.left);
                } else if (cur.right != null && root != cur.right) {
                    // 有右树，且右树没处理过
                    stack.push(cur.right);
                } else {
                    // 左右树没有或者都处理过了
                    System.out.print(cur.val + " ");
                    root = stack.pop();
                }
            }
        }
    }

    /**
     * 获取悄悄话传递花费的最大时间
     * https://fcqian.blog.csdn.net/article/details/134658206
     * 解法分析，给每个子节点累加上父节点的值，最后求的叶子节点最大值
     * 还有一个解法: 程序遍历二叉树每一层的最大值，再累加，这个解法需要先构建出二叉树；比较复杂。
     * @param times
     * @return
     */
    public static int getMaxConsumeTime(int[] times) {
        int ans = 0;

        LinkedList<Integer> queue = new LinkedList();
        queue.addLast(0);

        while (queue.size() > 0) {
            int fa = queue.removeFirst();
            int ch1 = 2 * fa + 1;
            int ch2 = 2 * fa + 2;

            boolean ch1_exist = ch1 < times.length && times[ch1] != -1;
            boolean ch2_exist = ch2 < times.length && times[ch2] != -1;
            if (ch1_exist) {
                times[ch1] += times[fa];
                queue.addLast(ch1);
            }

            if (ch2_exist) {
                times[ch2] += times[fa];
                queue.addLast(ch2);
            }

            if (!ch1_exist && !ch2_exist) {
                ans = Math.max(ans, times[fa]);
            }
        }

        return ans;
    }

    // 方法2更容易理解，结合了二叉树的层序遍历
    public static int getMaxConsumeTime2(int[] times) {
        int ans = 0;
        int len = times.length;
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(0);

        while (!queue.isEmpty()) {
            // 当前层节点数量
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            Integer curLevelMax = 0;

            // 遍历当前层的所有节点,并取出最大值
            for (int i = 0; i < levelSize; i++) {
                int fa = queue.removeFirst();
                currentLevel.add(fa);
                if (times[fa] != -1) {
                    curLevelMax = Math.max(curLevelMax, times[fa]);
                }

                int ch1 = 2 * fa + 1;
                if (ch1 < len) {
                    queue.add(ch1);
                }
                int ch2 = 2 * fa + 2;
                if (ch2 < len) {
                    queue.add(ch2);
                }
            }

            System.out.println(currentLevel.toString());
            ans += curLevelMax;
        }

        return ans;
    }

    /**
     * 根据数组构建二叉树
     * @param array
     * @return
     */
    public static TreeNode constructTree(int[] array) {
        if (array == null) {
            return null;
        }

        int index = 0;
        int length = array.length;

        TreeNode root = new TreeNode(array[index]);
        Deque<TreeNode> nodeQueue  = new LinkedList<>();
        nodeQueue.offer(root);
        TreeNode cur = null;

        while (index < length) {
            cur = nodeQueue.pollFirst();

            index++;
            if (index >= length) {
                return root;
            }

            int leftChild = array[index];
            cur.left = new TreeNode(leftChild);
            nodeQueue.offer(cur.left);

            index++;
            if (index >= length) {
                return root;
            }

            int rightChild = array[index];
            cur.right = new TreeNode(rightChild);
            nodeQueue.offer(cur.right);
        }

        return root;
    }


    /**
     * 二叉树层序遍历
     * * @param root
     */
    public static void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode cur = queue.pollFirst();
            if (cur.left != null) {
                queue.addLast(cur.left);
            }
            if (cur.right != null) {
                queue.addLast(cur.right);
            }
            System.out.print(cur.val + " ");
        }

        return;
    }

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(32);
//        root.left = new TreeNode(25);
//        root.right = new TreeNode(35);
//        root.left.left = new TreeNode(16);
//        root.left.right = new TreeNode(27);
//        root.right.left = new TreeNode(40);
//        root.right.right = new TreeNode(50);

//        System.out.println("先序遍历递归版：");
//        preOrder(root);
//
//        System.out.println("\n中序遍历递归版：");
//        inOrder(root);
//
//        System.out.println("\n后序遍历递归版：");
//        afterOrder(root);
//
//        System.out.println("\n先序遍历非递归版：");
//        preOrder2(root);
//
//        System.out.println("\n中序遍历非递归版：");
//        inOrder2(root);
//
//        System.out.println("\n后序遍历非递归版，两个栈实现：");
//        afterOrder2(root);
//
//        System.out.println("\n后序遍历非递归版，一个栈实现：");
//        afterOrder3(root);
//        int[] arr = new int[]{32, 25, 35, 16, 27};
//
////        TreeNode root = constructTree(arr);
//        System.out.println("层序遍历二叉树：");
//        levelOrder(root);
//        System.out.println();
        int[] times = new int[]{0, 9, 20, -1, -1, 15, 7, -1, -1, -1, -1, 3, 2};
        int ans1 = getMaxConsumeTime(times);
        System.out.println(ans1);
        int[] times2 = new int[]{0, 9, 20, -1, -1, 15, 7, -1, -1, -1, -1, 3, 2};
        int ans2 = getMaxConsumeTime2(times2);
        System.out.println(ans2);
    }
}
